#include<bits/stdc++.h>

using namespace std;
const int INF = 9999;//模拟的待删除空洞值INF
//手搓一个小顶堆
int data[1000] = {0}, size = 0;//size代表堆的容量,data存储数据，data[1]是堆顶元素

inline int &top() { return data[1]; }//堆顶元素
inline int &left(int i) { return data[2 * i]; }//返回左孩子，这里要注意引用返回值可以避免值拷贝
inline int &right(int i) { return data[2 * i + 1]; }//返回右孩子，这里要注意引用返回值可以避免值拷贝
inline int &parent(int i) { return data[i / 2]; } //返回父节点，这里要注意引用返回值可以避免值拷贝

void push(int x) {//堆插入元素，调整堆结构
    data[++size] = x;
    int k = size;
    while (k > 1 && data[k] < parent(k)) {
        swap(data[k], parent(k));
        k /= 2;
    }
}

//这个比较有难度，主要是调整到最后一层的时候要把空洞值INF和最有一个data[size]交换，避免空洞
void pop() {
    if (size == 0)return;
    data[1] = INF;
    int k = 1;
    swap(data[k], data[size--]);//感谢225班zxw的测试~
    while (2 * k <= size) {//调整保证小顶堆的性质
        if (data[k] <= left(k) && data[k] <= right(k))break;
        if (left(k) > right(k)) {
            swap(data[k], right(k));
            k = k * 2 + 1;
        } else {
            swap(data[k], left(k));
            k = k * 2;
        };
    }   
}

int main() {
    srand(time(NULL));
    size = 0;//初始化堆
    for (int i = 1; i <= 10; i++) {
        int k = rand() % 100;
        cout << k << " ";
        push(k);
    }
    cout << endl;
    while (size >= 1) {
        cout << top() << " ";
        pop();
    }
    return 0;
}